package Demo68;

/**
 * 字符相乘
 * https://leetcode.cn/problems/multiply-strings/
 */
class Solution {
    /**
     * 优化无进位相乘
     */
    public String multiply(String num1, String num2) {
        // 1. 准备工作
        int len1 = num1.length(),len2 = num2.length();
        char[] ch1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] ch2 = new StringBuffer(num2).reverse().toString().toCharArray();
        int[] tmp = new int[len1 + len2 - 1];
        // 无进位相加
        for(int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                tmp[i + j] += (ch1[j] - '0') * (ch2[i] - '0');
            }
        }
        int cur = 0, t = 0;
        StringBuffer ret = new StringBuffer();
        while(cur < len1 + len2 - 1 || t != 0) {
            if(cur < len1 + len2 - 1) t += tmp[cur++];
            ret.append(t % 10);
            t /= 10;
        }
        // 处理前导0
        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            ret.deleteCharAt(ret.length() - 1);
        }
        return ret.reverse().toString();
    }
    /**
     * 无进位相乘再相加
     */
    public String multiply2(String num1, String num2) {
        // 处理边界
        if(num1.length() == 1 && (num1.charAt(0) == '0')
            || num2.length() == 1 && (num2.charAt(0) == '0')) {
            return "0";
        }
        // 算前处理
        StringBuffer cur1 = new StringBuffer(num1);
        StringBuffer cur2 = new StringBuffer(num2);
        cur1.reverse();
        cur2.reverse();

        int len1 = cur1.length();
        int len2 = cur2.length();
        // 存放相乘后的值
        int[] count = new int[(len1 + len2 - 1)];

        for(int i = 0; i < len1;i++) {
            for(int j = 0; j < len2; j++) {
                count[i + j] += (cur1.charAt(i) - '0') * (cur2.charAt(j) - '0');
            }
        }
        StringBuffer ret = new StringBuffer();
        int tmp = 0;
        for(int i = 0; i < count.length; i++) {
            tmp += count[i];
            ret.append(tmp % 10);
            tmp /= 10;
        }
        if(tmp != 0) ret.append(tmp);

        return ret.reverse().toString();
    }

    /**
     * 模拟模拟乘法实现
     * 先逆序字符串
     * 然后通过模拟乘法运算,最后再一次性翻转,返回
     */
    public String multiply1(String num1, String num2) {
        // 校验0的情况
        if(num1.length() == 1 && (num1.charAt(0) == '0')
            || num2.length() == 1 && (num2.charAt(0) == '0') ) {
            return "0";
        }

        StringBuffer cur1 = new StringBuffer(num1);
        StringBuffer cur2 = new StringBuffer(num2);
        // 翻转两个字符串
        cur1.reverse();
        cur2.reverse();

        StringBuffer ret = new StringBuffer();
        for(int i = 0; i < cur2.length();i++) {
            // 存储每次循环的结果
            StringBuffer cur = new StringBuffer();
            // 处理结尾的0
            for(int m = 0; m < i;m++) cur.append(0);
                // 处理每次循环的进位
            int tmp = 0 ;
            for(int j = 0; j < cur1.length();j++) {
                tmp += (cur1.charAt(j) - '0') * (cur2.charAt(i) - '0');
                cur.append(tmp % 10);
                tmp /= 10;
            }
            // 处理进位的边界值
            if(tmp != 0) {
                cur.append(tmp);
            }
            // 将cur的值添加到ret中
            ret = addBinary(cur,ret);
        }
        ret.reverse();
        return ret.toString();
    }

    private StringBuffer addBinary(StringBuffer cur, StringBuffer ret) {
        StringBuffer tmp = new StringBuffer();
        int len1 = cur.length(), len2 = ret.length();
        int i = 0, j = 0, t = 0;
        while(i < len1 || i < len2 || t != 0) {
            if(i < len1) {
                t += (cur.charAt(i) - '0');
            }
            if(i < len2) {
                t +=(ret.charAt(i) - '0');
            }
            tmp.append(t % 10);
            t /= 10;
            i++;
        }
        return tmp;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String multiply = solution.multiply("123", "456");
        System.out.println(multiply);
    }
}